package solution;

import java.util.*;

/**
 * @author zhangmin
 * @create 2021-09-25 15:16
 */
public class Solution_9graph {


    /** ===========================================================================================================================
     * 图遍历--797. 所有可能的路径
     * 1. 从 0 号点出发，使用栈记录路径上的点。每次我们遍历到点 n-1，就将栈中记录的路径加入到答案中。
     * */
    List<List<Integer>> ans=new ArrayList<List<Integer>>();
    //Java堆栈Stack类已经过时，Java官方推荐使用Deque双端队列替代Stack使用。
    Deque<Integer> stack=new ArrayDeque<>();

    public void dfs(int[][] g,int x,int n){
        if (x==n){
            ans.add(new ArrayList<>(stack));
            return;
        }
        for (int y:g[x]) {
            stack.offerLast(y);
            dfs(g,y,n);
            stack.pollLast();
        }
    }

    public List<List<Integer>> allPathsSourceTarget1(int[][] graph) {
        int n=graph.length;
        stack.offerLast(0);
        dfs(graph,0,n-1);
        return ans;
    }

    //2.不使用堆栈
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        LinkedList<Integer> path=new LinkedList<>();
        traverse(graph,0,path);
        return ans;
    }
    /* 图的遍历框架 */
    void traverse(int[][] graph, int s, LinkedList<Integer> path) {
        path.addLast(s);
        int n=graph.length;
        if (s==n-1){
            ans.add(new LinkedList<>(path));
            path.removeLast();
            return;
        }
        // 递归每个相邻节点
        for (int v: graph[s]) {
            traverse(graph,v,path);
        }
        // 从路径移出节点 s
        path.removeLast();
    }

    /** ===========================================================================================================================
     * 拓扑排序---207. 课程表
     *判断是否有环，当有循环依赖时无法完成课程
     * 其实这种场景在现实生活中也十分常见，比如我们写代码 import 包也是一个例子，必须合理设计代码目录结构，否则会出现循环依赖，编译器会报错，所以编译器实际上也使用了类似算法来判断你的代码是否能够成功编译。
     * */
    List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        //先构建图
        List<Integer>[] g=new LinkedList[numCourses];
        for (int i = 0; i < numCourses; i++) {
            g[i]=new LinkedList<>();
        }
        for (int[] edge:prerequisites ) {
            int from=edge[1];
            int to=edge[0];
            g[from].add(to);
        }
        return g;
    }
    // 防止重复遍历同一个节点
    boolean[] visited;
    // 记录一次 traverse 递归经过的节点
    boolean[] onPath;
    boolean hasCycle=false;
    // 从节点 s 开始 BFS 遍历，将遍历过的节点标记为 true
    void traverseBFS(List<Integer>[] graph, int s) {
        if(onPath[s])
            hasCycle=true;
        if (visited[s])
            return;
        visited[s]=true;
        //开始遍历s，将s放到路径上
        onPath[s]=true;
        for (int v:graph[s]) {
            traverseBFS(graph,v);
        }
        //遍历s结束，s回溯
        onPath[s]=false;
    }
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] g=buildGraph(numCourses,prerequisites);
        visited=new boolean[numCourses];
        onPath=new boolean[numCourses];
        for (int i = 0; i < numCourses; i++) {
            traverseBFS(g,i);
        }
        return !hasCycle;
    }

    /** ===========================================================================================================================
     * 拓扑排序--210. 课程表 II
     * 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites，返回你为了学完所有课程所安排的学习顺序。
     *先判断是否有环，没有环的时候将后序遍历的结果反转就是拓扑排序的结果
     *  */
    List<Integer> postOrder=new ArrayList<>();
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //先判断是否有环
        if (!canFinish(numCourses,prerequisites))
            return new int[]{};
        List<Integer>[] g = buildGraph(numCourses, prerequisites);
        visited=new boolean[numCourses];
        //进行DFS
        for (int i = 0; i < numCourses; i++) {
            traverseDFS(g,i);
        }
        Collections.reverse(postOrder);
        int res[]=new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            res[i]=postOrder.get(i);
        }
        return res;
    }
    void traverseDFS(List<Integer>[] graph, int s) {
        if (visited[s])
            return;
        visited[s]=true;
        for (int v:graph[s]) {
            traverseBFS(graph,v);
        }
        postOrder.add(s);
    }

    /**===========================================================================================================================
     *  二分图--785. 判断二分图
     *  DFS遍历图，并记录颜色即可
     *  */
    boolean[] color;//记录节点颜色，true和false是两种颜色
    boolean[] visited3;
    boolean isbipartite=true;//记录最终结果是否是二分图
    void traverse(int[][] graph,int s){
        if (!isbipartite) return;//确定不是二分图了
        visited3[s]=true;
        for (int next:graph[s]) {
            if (!visited3[next]){
                color[next]=!color[s];
                traverse(graph,next);
            }else {
                //next已经被访问过了，判定她和s的颜色
                if (color[next]==color[s]){
                    isbipartite=false;
                }
            }
        }
    }
    public boolean isBipartite(int[][] graph) {
        int n=graph.length;
        visited3=new boolean[n];
        color=new boolean[n];
        //有可能不连通，所以需要遍历每个节点
        for (int i = 0; i < n; i++) {
            if (!visited3[i]){
                traverse(graph,i);
            }
        }
        return isbipartite;
    }
    /**===========================================================================================================================
     *  二分图--886. 可能的二分法
     *  给定一组 n 人（编号为 1, 2, ..., n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。
     * 给定整数 n 和数组 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和  bi的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。
     * 思路：构建图，然后判定是否是二分图即可
     *  */
    boolean[] twoTeam;
    boolean[] visited4;
    boolean res=true;
    List<Integer>[] buildGraph(int[][] dislikes,int n){
        List<Integer>[] graph=new LinkedList[n];
        for (int i = 0; i < n; i++) {
            graph[i]=new LinkedList<>();
        }
        for (int[] edge:dislikes) {
            //无向图，两个节点都要加入对方,节点下标是从1开始的
            graph[edge[0]-1].add(edge[1]-1);
            graph[edge[1]-1].add(edge[0]-1);
        }
        return graph;
    }
    void traverse(List<Integer>[] graph,int s){
        if (!res) return;
        visited4[s]=true;
        for (int next:graph[s]) {
            if (visited4[next]){
                //判定两个节点的颜色
                if (twoTeam[next]==twoTeam[s]){
                    res=false;
                }
            }else {
                //将下一个节点标记为不同颜色
                twoTeam[next]=!twoTeam[s];
                traverse(graph,next);
            }
        }
    }
    public boolean possibleBipartition(int n, int[][] dislikes) {
        twoTeam=new boolean[n];
        visited=new boolean[n];
        List<Integer>[] graph = buildGraph(dislikes, n);
        for (int i = 0; i < n; i++) {
            if (!visited4[i]){
                traverse(graph,i);
            }
        }
        return res;
    }
    /** ===========================================================================================================================
     * 1584. 连接所有点的最小费用
     * 给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。
     * 连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。
     * 请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
     * 思路：先生成所有的边和权重，然后再执行 Kruskal 算法即可
     *  */
    //并查集用于判定树
    class UF{
        int count;
        int[] parent;
        public UF(int n){
            this.count=n;
            this.parent=new int[n];
            for (int i = 0; i < n; i++) {
                parent[i]=i;
            }
        }
        int find(int x){
            //返回x的根,并顺便进行路径压缩
            if (parent[x]!=x){
                parent[x]=find(parent[x]);
            }
            return parent[x];
        }
        void Union(int p,int q){
            //p，q连通
            int rootp = find(p);
            int rootq = find(q);
            if (rootp==rootq) return;
            parent[rootp]=rootq;
            count--;
        }
        boolean isConnected(int p,int q) {
            int rootp = find(p);
            int rootq = find(q);
            return rootq == rootp;
        }
    }
    public int minCostConnectPoints(int[][] points) {
        int n=points.length;
        List<int[]> edges=new ArrayList<>();
        //生成所有边和权重
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                int x1=points[i][0],y1=points[i][1];
                int x2=points[j][0],y2=points[j][1];
                edges.add(new int[]{i,j,Math.abs(x1-x2)+Math.abs(y1-y2)});
            }
        }
        //按照权重从小到大排序
        Collections.sort(edges,(a,b)->{
            return a[2]-b[2];
        });
        int res=0;
        UF uf=new UF(n);
        for (int[] edge:edges) {
            if (uf.isConnected(edge[0],edge[1])) continue;
            res+=edge[2];
            uf.Union(edge[0],edge[1]);
        }
        return res;
    }

    /** ===========================================================================================================================
     * 277 搜索名人
     * 给你 n 个人的社交关系（你知道任意两个人之间是否认识），然后请你找出这些人中的「名人」。所谓「名人」有两个条件：1、所有其他人都认识「名人」。2、「名人」不认识任何其他人。--它保证了人群中最多有一个名人
     * 只要观察任意两个候选人的关系，我一定能确定其中的一个人不是名人，把他排除。
     *  */
    // 可以直接调用，能够返回 i 是否认识 j
    boolean knows(int i, int j){
        return true;
    }
    // 请你实现：返回「名人」的编号
    int findCelebrity(int n) {
        if (n==1)return 0;
        // 将所有候选人装进队列
        LinkedList<Integer> q=new LinkedList<>();
        for (int i = 0; i < n; i++) {
            q.addLast(i);
        }
        while (q.size()>=2){
            int cand=q.removeFirst();
            int other=q.removeFirst();
            if (knows(cand,other)||!knows(other,cand)){
                // cand 不可能是名人，排除，让 other 归队
                q.addFirst(other);
            }else {
                q.addFirst(cand);
            }
        }
        // 现在排除得只剩一个候选人，判断他是否真的是名人
        int cand=q.removeFirst();
        for (int other = 0; other < n; other++) {
            if (cand==other){
                continue;
            }
            if (!knows(other,cand)||knows(cand,other)){
                return -1;
            }
        }
        return cand;
    }
    //空间优化:时间复杂度为 O(N)，空间复杂度为 O(1)
    int findCelebrity1(int n) {
        if (n==1)return 0;
        int cand=0;
        for (int other = 1; other < n; other++) {
            if (knows(cand,other)||!knows(other,cand)){
                // cand 不可能是名人，排除
                // 假设 other 是名人
                cand=other;
            }else {
                // other 不可能是名人，排除
                // 什么都不用做，继续假设 cand 是名人
            }
        }
        // 现在的 cand 是排除的最后结果，但不能保证一定是名人
        for (int other = 0; other < n; other++) {
            if (cand==other){
                continue;
            }
            if (!knows(other,cand)||knows(cand,other)){
                return -1;
            }
        }
        return cand;
    }
    /** ===========================================================================================================================
     *  743. 网络延迟时间
     *  n 个网络节点，标记为 1 到 n。给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点，
     *  wi 是一个信号从源节点传递到目标节点的时间。现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
     *  思路：经典的最短路径问题，套用模板
     *  */
    //Dijkstra 算法的框架
    class State{
        //图中节点id
        int id;
        //从start到当前节点的距离
        int distFromStart;
        State(int id,int distFromStart){
            this.id=id;
            this.distFromStart=distFromStart;
        }
    }
    //返回从start作为起点到其他节点的最短距离
    int[] dijkstra(int start,List<int[]>[] graph){
        int n=graph.length;
        // 定义：distTo[i] 的值就是起点 start 到达节点 i 的最短路径权重
        int[] distTo=new int[n];
        Arrays.fill(distTo,Integer.MAX_VALUE);
        distTo[start]=0;
        Queue<State> pq=new PriorityQueue<>((a,b)->{
            return a.distFromStart-b.distFromStart;
        });
        //从start开始遍历
        pq.offer(new State(start,0));
        while (!pq.isEmpty()){
            State cur = pq.poll();
            int curId=cur.id;
            int curDistFromStart=cur.distFromStart;
            if (curDistFromStart>distTo[curId]){
                //当前节点并不会使得到cur的路径变短
                continue;
            }
            for (int[] neighbor:graph[curId]) {
                int nextId=neighbor[0];
                int distToNextNode=distTo[curId]+neighbor[1];
                if (distTo[nextId]>distToNextNode){
                    distTo[nextId]=distToNextNode;
                    pq.offer(new State(nextId,distToNextNode));
                }
            }
        }
        return distTo;
    }
    public int networkDelayTime(int[][] times, int n, int k) {
        List<int[]>[] graph=new LinkedList[n];
        for (int i = 0; i < n; i++) {
            graph[i]=new LinkedList<>();
        }
        //构造图
        for (int[] edge:times) {
            int from=edge[0]-1,to=edge[1]-1,weight=edge[2];
            graph[from].add(new int[]{to,weight});
        }
        // 启动 dijkstra 算法计算以节点 k 为起点到其他节点的最短路径
        int[] distTo = dijkstra(k-1, graph);
        int res=0;
        for (int i = 0; i < distTo.length; i++) {
            if (distTo[i]==Integer.MAX_VALUE) return -1;
            res=Math.max(res,distTo[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        Solution_9graph object=new Solution_9graph();
        int[][] g=new int[][]{{1,2},{3},{3},{}};
        System.out.println(object.allPathsSourceTarget1(g));
    }
}
